package jianzhi_offer;

import java.util.HashSet;
//剑指offer第一题：找出重复的数字

//两种思路：一是用替换的思想（将原数组中的内容作为新数组中的下标，只要出现就加一。如果大于二返回新数组对应的下标就行）
//二是使用哈希表（hashSet）
public class test1 {
    public int duplicate (int[] numbers) {
        if (numbers.length == 0) {
            return -1;
        }
        // int n = numbers.length;
        // int[] ret = new int[n];
        // for(int i :numbers) {
        //     ret[i]++;
        //     if(ret[i] >= 2) {
        //         return i;
        //     }
        // }
        // return -1;

        //可以理解为判断某个数在set中是否存在（不存在就继续添加）
        HashSet<Integer> set = new HashSet<>();
        for(int i : numbers) {
            if(set.contains(i)) {
                return i;
            }else {
                set.add(i);
            }
        }
        return -1;
    }
}
